package com.peng.tree.test_code.dp;

import com.peng.tree.Node;

/**
 * 给定头节点，获得树上最大的搜索子树的头节点
 * <p>
 * 分情况讨论，最大搜索子树与当前头X是否有关系：
 * 1、与X无关，说明最大搜索子树出现在头X的左树或者右树上
 * 2、与X有关，说明最大搜索子树是以X为头的整棵树本身：
 * 此时需要满足：
 * 1、右子树最小值 > x节点值   >左子树max值
 * 2、左右子树都为搜索二叉树
 * 如果满足，那么最大搜索子树头自然为X
 */
public class Test10_GetMaxSubSearchTreeHead {

    public static Node getMaxSubSearchTreeHead(Node node) {
        if (node == null) {
            return null;
        }

        return process(node).head;


    }

    public static TreeInfo process(Node node) {
        if (node == null) {
            return null;
        }

        TreeInfo leftInfo = process(node.left);
        TreeInfo rightInfo = process(node.right);


        int max = node.value;
        int min = node.value;
        int allSize = 1;

        int p1 = -1;//左树的最大搜索子树个数
        int p2 = -1;//右树的最大搜索子树个数
        int p3 = -1;//整棵树的最大搜索子树个数

        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            allSize += leftInfo.allSize;
            p1 = leftInfo.maxSubSearchTreeSize;
        }

        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            allSize += rightInfo.allSize;
            p2 = rightInfo.maxSubSearchTreeSize;
        }

        boolean leftSearchable = leftInfo == null || leftInfo.allSize == leftInfo.maxSubSearchTreeSize;
        boolean rightSearchable = rightInfo == null || rightInfo.allSize == rightInfo.maxSubSearchTreeSize;
        //左树是搜索二叉 && 右树是搜索二叉
        if (leftSearchable && rightSearchable) {
            boolean leftLess = leftInfo == null || leftInfo.max < node.value;
            boolean rightMore = rightInfo == null || rightInfo.min > node.value;
            if (leftLess && rightMore) {
                p3 = allSize;
            }
        }
        int maxSubSize = Math.max(Math.max(p1, p2), p3);
        Node head = maxSubSize == p1 ? leftInfo.head : (maxSubSize == p2 ? rightInfo.head : node);
        return new TreeInfo(maxSubSize, max, min, allSize, head);


    }

    public static void main(String[] args) {
        Node node = new Node(30);
        Node node2 = new Node(20);
        Node node3 = new Node(40);
        Node node4 = new Node(10);
        Node node5 = new Node(25);
        Node node6 = new Node(32);
        Node node7 = new Node(60);
        Node node8 = new Node(6);
        Node node9 = new Node(13);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;

         /*
                   30
             20              40
           10    15         32     60
         6   13

         */

        System.out.println(getMaxSubSearchTreeHead(node).value);
    }

    static class TreeInfo {
        int maxSubSearchTreeSize;
        int max;
        int min;
        int allSize;
        Node head;

        public TreeInfo(int maxSubSearchTreeSize, int max, int min, int allSize, Node head) {
            this.maxSubSearchTreeSize = maxSubSearchTreeSize;
            this.max = max;
            this.min = min;
            this.allSize = allSize;
            this.head = head;
        }
    }


}
